#include "KMP_pattern_match.h"

int *build_next(const char *ptn, int *next){
    int i = 0; //int j = 0;// j == -1
    int j = -1;
    int len = strlen(ptn);

    next[0] = -1;
    while(i < len){
        if(j == -1 ||  ptn[i] == ptn[j]){
            next[++i] = ++j;
        }
        else{
            j = next[j];
        }
    }
    return next;
}   
diff_t KMP_match(const char *str, const char *ptn, int pos){
    int i = pos; int j = 0;
    int len_str = strlen(str); int len_ptn = strlen(ptn);
    int *next = (int*)malloc((len_ptn + 3) * sizeof(int));
    next = build_next(ptn, next);
    while(i < len_str && j < len_ptn){
        if( str[i] == ptn[j]){ 
            ++i;++j;
        }
        else{
            if(j == 0) { ++i;}
            /*
             *       if j equals to 0 means it is non-matched with str[i]
             *   and will be assigned to -1. It's the situation we shall treat 
             *   specially
             */ 
            else { j = next[j];}
        }
    }
    return j == len_ptn ? i - len_ptn : -1;
}



